package com.company.ljh.hard;
//给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
//
//算法的时间复杂度应该为 O(log (m+n)) 。
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
public class 两个正序数组中位数 {
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (((nums1.length+nums2.length) % 2) ==1)
            return findKNumber(nums1,nums2,(nums1.length+nums2.length+1)/2);
        else
            return (findKNumber(nums1,nums2,(nums1.length+nums2.length)/2)+findKNumber(nums1,nums2,(nums1.length+nums2.length)/2+1))/2;

    }


    /**
     * 寻找第k大的数
     * 思路：找两个数组第k/2大的数，第一个数组的k/2的数小于第二个数组，则第一个数组的前k/2不可能存在第k大的数,因此去掉第一个数组前k/2个数，k变为2/k
     * 特殊情况:
     *  1.k为1时,只需要比较两个数组第一个数大小即可
     *  2.一个数组为空时，k大的数即为另一个数组第k个数
     *  3.当一个数组的大小小于k/2,那么需要比较两个数组加起来为k的数 （数组1：[3]数组2[1,3,4,5]  k为4,需要比较数组1第1个数和数组2第3个数）
     *
     */

    public static double findKNumber(int[] nums1, int[] nums2,int k){
        if (nums1.length == 0){
            return nums2[k-1];
        }
        if (nums2.length == 0){
            return nums1[k-1];
        }
        if (k == 1){
            return nums1[0]<nums2[0]?nums1[0]:nums2[0];
        }
        int index1 = k/2;
        int index2 = k/2;
        if (k/2 > nums1.length){
            index1 = nums1.length;
            index2 = k-index1;
        }
        if (k/2 > nums2.length){
            index2 = nums2.length;
            index1 = k-index2;
        }
        if (nums1[index1-1] < nums2[index2-1]){
            int[] nums = new int[nums1.length - index1];
            System.arraycopy(nums1,index1,nums,0,nums1.length - index1);
            return findKNumber(nums,nums2,k-index1);
        }else {

            int[] nums = new int[nums2.length - index2];
            System.arraycopy(nums2,index2,nums,0,nums2.length - index2);
            return findKNumber(nums1,nums,k-index2);
        }

    }

    public static void main(String[] args) {
        int[] num1 = new int[]{1,3,4,6};
        int[] num2 = new int[]{2};
        double kNumber = findKNumber(num1, num2, 4);
        System.out.println(kNumber);
        System.out.println(findMedianSortedArrays(num1,num2));
    }
}
